package 力扣;

import java.util.ArrayList;

/**
 * @author yyq
 * @create 2021-12-28 18:13
 * 最大子数组和
 */
public class Hot100_53 {
    public static void main(String[] args) {
        int[] a={-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(Hot100_53.maxSubArray(a));

    }
    // 输入形式 nums = [-2,1,-3,4,-1,2,1,-5,4]
    public static   int maxSubArray(int[] nums) {
        // 用来记下当前开始和结束
        int start = -1;
        int end = -1;
        int sum = 0;
        int length = nums.length;
        ArrayList<logs> logsList=new ArrayList<>();

        if(length==0)
            return 0;
        if(length==1)
            return nums[0];

        for (int i = 0; i < length; i++) {

            if(nums[i]<0 && start==-1) continue;
            if(nums[i]>0){
                if(start == -1) start=i;
                sum = sum + nums[i];
            }
            if(nums[i]<0){
                if(sum + nums[i]>0){
                    sum = sum + nums[i];
                }
                int flag=0;
                if(sum + nums[i]<0) {

                    int add=0;
                    for(int k=i+1;k<length;k++){
                        if(nums[k]>=0){
                            add = add+nums[k];
                        }
                        if(nums[k]<0){
                            flag=k;
                            break;
                        }
                    }
                    if(sum + nums[i] < add){
                        end = i-1;
                        logsList.add(new logs(start,end,sum));
                        start=-1;
                        end=-1;
                        sum=0;
                        i=flag;
                    }
                }
            }
        }

        int flag=0;

        for (int i = 1; i < logsList.size(); i++) {
            if(logsList.get(flag).sum < logsList.get(i).sum){
                flag = i;
            }
        }


        return logsList.get(flag).sum;
    }
}

class logs{
    int start;
    int end;
    int sum;

    public logs(int start, int end, int sum) {
        this.start = start;
        this.end = end;
        this.sum = sum;
    }

    public logs() {

    }
}

